МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра ЕОМ / Звіт лабораторної роботи №1 «Застосування генетичних алгоритмів для вирішення задач оптимізації» з дисципліни: «Комп'ютерні системи штучного інтелекту»  Мета роботи: навчитися розв’язувати задачі оптимізації за допомогою генетичного алгоритму, навчитися програмно реалізовувати генетичний алгоритм.  Генетичний алгоритм – потужний інструмент для вирішення складних задач. Він знайшов своє застосування серед задач оптимізації, інженерії, штучного інтелекту. В основу алгоритму покладено принципи біології та генетики – створення популяції індивідів, кожен з яких представляється у вигляді хромосоми. Своїм існуванням генетичні алгоритми завдячують спробам наслідування природних процесів, які відбуваються серед живих організмів – селекції та еволюції популяції живих істот. Ідею генетичного алгоритму у 1975 році запропонував Джон Холланд (J.H.Holland). Він припустив, що складений відповідним чином алгоритм біологічної еволюції може бути покладений в основу розв’язання складних проблем. Представлення об’єктів.Біологічно кожен організм може бути представлений своїм фенотипом ( котрий визначає чим є об’єкт у реальному світі) та генотипом ( котрий містить інформацію про цей об’єкт на рівні хромосомного набору). Кожен ген, тобто елемент інформації генотипу, містить своє відображення у фенотипі. Генетичні алгоритми моделюють природну еволюцію та використовуються здебільшого для розв’язання задач оптимізації. Генетичний алгоритм перейняв термінологію з генетики: хромосома (елемент популяції), популяція ( випадковий набір допустимих розв’язків), алель (значення гена), ген (елемент хромосоми, двійковий розряд), локус (позиція гена у хромосомі), алель (значення гена), покоління ( результат наступної ітерації роботи алгоритму), фенотип ( числове значення хромосоми). Генетичний алгоритм.Класичний генетичний алгоритм зображений на рис.1 /Рис.1 Блок-схема роботи генетичного алгоритму. 1. Створення початкової популяції. На першому етапі роботи створюємо певну початкову популяцію. Навіть якщо вона буде неконкурентоспроможною алгоритм сам перетворить її у «живу» популяцію. З популяції випадково вибираємо N хромосом у вигляді бітових ланцюжків довжиною L. Вводимо поняття номеру популяції К ( для початкової К=0). 2. На даному етапі необхідно обчислити значення функції відповідності кожної хромосоми. Чим вище значення функції, тим вища якість хромосоми. 3. Умови зупинки алгоритму . Алгоритм припиняє свою роботу у наступних випадках: коли досягнуто шуканого значення( із заданою точністю); коли подальша робота алгоритму не може покращити отриманий результат; коли був вичерпаний заданий ліміт часу чи кількості ітерацій. У випадку зупинки алгоритму виводимо найкращу хромосому. 4. Відбір хромосоми. Обчисливши значення функції відповідності відбираємо нащадків хромосом із найбільшим значенням. Зазвичай відбір проводиться методом рулетки. Результатом роботи операції є батьківський пул з N хромосом. Відповідно його розмір збігається із розміром початкової популяції. 5. Створення нової популяції. Створення нової популяції досягається застосуванням генетичних операторів. За їх допомогою ми утворюємо нову популяцію нащадків. В класичному алгоритмі використовують два генетичних оператори – схрещування та мутація. При цьому схрещування відбувається завжди, а мутація доволі рідко. При реалізації генетичного алгоритму задається ймовірність схрещування Pc (0,5≤ Pc ≥ 1) та ймовірність мутації Pm (0 ≤ Pm ≥ 0,5) .  Сутність методу рулетки для селекції хромосом (roulette wheel selection)Метод моделює випадковий вибір, за аналогією рулетки в казино. Рулетка ділиться на частини, кожна з яких відповідає кожній хромосомі. Розмір секції рулетки є пропорційним до значення функції відповідності цієї хромосоми. Чим більше значення функції відповідності, тим більша частина кола відповідає йому на рулетці і навпаки. Математично це можна...